package com.lihepeng.leecode.linkedList;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 删除链表倒数第N 个节点
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * <p>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution19 {
    // 使用快慢指针方法解决该问题
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode dumpNode = new ListNode(-1);
        dumpNode.next = head;
        ListNode slow = dumpNode;
        ListNode fast = dumpNode;
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        // 快节点先往前行走N个节点，然后满节点一块走，当快节点走到头这个时候满节点就在倒数N个节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dumpNode.next;
    }

    // 删除倒数第n个节点
    public ListNode removeNthFromEnd01(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode dumpNode = new ListNode(-1);
        dumpNode.next = head;
        ListNode fastNode = dumpNode;
        ListNode slowNode = dumpNode;
        for (int i = 0; i < n + 1; i++) {
            fastNode = fastNode.next;
        }
        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        slowNode.next = slowNode.next.next;
        return dumpNode.next;

    }

    public ListNode removeNthFromEnd02(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode currentNode = head;
        Map<Integer, ListNode> map = new HashMap<>();
        int currentCount = 1;
        while (currentNode != null) {
            map.put(currentCount++, currentNode);
            currentNode = currentNode.next;
        }
        ListNode listNode = map.get(currentCount - n);
        ListNode preNode = map.get(currentCount - n - 1);
        /*if (map.size() ==0|| map.size() ==1){
            return null;
        }*/
        if (preNode != null) {
            preNode.next = listNode.next;
        } else {
            return listNode.next;
        }
        return head;

    }
    public ListNode removeNthFromEnd03(ListNode head, int n) {
        ListNode dumpyNode = new ListNode(-1);
        dumpyNode.next = head;
        ListNode fromEnd = findFromEnd(dumpyNode, n+1);
        fromEnd.next = fromEnd.next.next;
        return dumpyNode.next;
    }

    /**
     * 删除倒数第 K 个节点
     * 使用快慢指针的方法
     * @param head
     * @param n
     * @return
     */
    public ListNode findFromEnd(ListNode head, int n) {
        ListNode p1 = head;
        ListNode p2 = head;
        // 先让p1 向前走 n 次
        for (int i=0;i<n;i++) {
            p1 = p1.next;
        }
        while (p1!=null) {
            p1=p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    @Test
    public void runTest() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        /*ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;*/
        n1.next = n2;
        ListNode listNode = this.removeNthFromEnd02(n1, 2);
        System.out.println(listNode);
    }

}
